# 改写文法，消除左递归，消除左因子
result_1 = []  # 用来存储消除左递归后的结果
result_2 = []  # 用来存储提取左因子后的结果


def read_grammar():
    """读入文法中所有生成式"""
    grammar = []   # 用来存储输入每个产生式的列表
    num = int(input("请输入文法式子个数："))
    print("请依输入各式子：")
    for i in range(num):
        context_str = input()
        grammar.append(context_str)
    return grammar  # 返回文法产生式的列表


def judge_result(grammar):
    """判断左递归，并返回结果"""
    print("-------------消除左递归-------------")
    print("判断过程：")
    for i in grammar:   # 遍历文法中的每一个产生式
        flag = 0   # flag用来标记第i个产生式是否存在直接左递归，初始化为0，若存在，则赋值为1
        List = i.split('->')  # 将'→'左右分隔开，分别存入列表
        A = List[0]  # A存储 '→'左边的非终结符
        B = List[1]  # B存储'→'右边的边的非终结符或者终结符所构成的字符串
        B = B.split('|')  # 再将B中的多个候选分隔开，B中存储的是多个候选
        for j in B:  # 遍历B中的每个候选
            if j[0] == A:  # 如果B中候选的第一个字符以A中的非终结符开头，则存在直接左递归
                flag = 1  # 出现左递归标记该式子
                # 提示该式存在左递归的信息
                print(i, " 存在左递归！需要消除！")
                eliminate_left_recursion(A, B)  # 调用消除左递归函数消除左递归
                break
        if flag == 0:
            # 若第i个产生式子不存在左递归
            print(i, " 此式不需要消除递归！")
            result_1.append(i)  # 直接将该式加入到结果列表中


def eliminate_left_recursion(A, B):
    """消除左递归"""
    str1 = A + '->'  # str1用来存储消除左递归后产生的第一个式子
    str2 = A + '\'' + '->'  # str2用来存储消除左递归产生的第二个式子
    α = []
    β = []
    # 对候选进行判断划分到α和β中
    for i in B:
        if i[0] != A:
            β.append(i)
        else:
            α.append(i.split(A)[1])
    for each in β:
        str1 += each + A + '\'' + '|'
    for each in α:
        str2 += each + A + '\'' + '|'
    str1 = str1.strip('|')  # 去除末尾的|符号
    str2 += 'ε'  # 在末尾加ε
    # 将消除直接左递归后的结果加入结果列表中
    result_1.append(str1)
    result_1.append(str2)

def get_left_factor(result):
    """提取左因子"""
    print("-------------提取左因子-------------")
    print("判断过程：")
    for i in result:
        depart = i.split('->')
        select = depart[1].split('|')  # 候选项列表
        if len(select) == 1:  # 候选项数为1时，不需要提取左因子，退出循环即可
            print(i, " 此式子不需提取左因子！")
            result_2.append(i)
            continue
        else:   # 否则需要提取左因子
            # 先按照首字母将列表各候选分类
            s = set()
            d = dict()
            for j in select:
                s.add(j[0])  # 遍历各个候选将首字母放入集合中，注意会去重
            for k in s:  # 遍历首字母集合，把它们当作字典的键值
                d.setdefault(k, [])
            for j in select:
                d[j[0]].append(j)  # 将具有相同首字母前缀放到自字典的一个key中

            # 对列表中各元素进行最大前缀的提取
            for value_list in d.values():  # 遍历每一个具有相同首字母的候选值，提取他们的公共最长前缀
                if len(value_list) == 1:  # 如果首字母相同的候选只有一个，不需要提取左因子
                    result_2.append(i)
                    print(i, " 此式子不需提取左因子！")
                    break
                else:
                    print(i, " 此式存在左因子，需提取左因子！")
                    s_min = min(value_list)
                    s_max = max(value_list)
                    longest_common_prefix =''
                    for index, value in enumerate(s_min):
                        if value != s_max[index]:  # 匹配到一个不相等的字符
                            longest_common_prefix = s_min[:index]  # 记录最大公共前缀
                            break
                    # print("最大公共前缀：", longest_common_prefix)
                    result_2.append(depart[0]+'→'+longest_common_prefix+depart[0]+'\'')
                    x = ""
                    for k in value_list:
                        x += k.replace(longest_common_prefix, "") + '|'  # 除去最大公共前缀后剩余部分
                    x = depart[0]+'\''+'->'+x
                    x = x.strip('|')  # 去除末尾的|符号
                    result_2.append(x)  # 添加到结果列表中






if __name__ == '__main__':
    # 用户输入文法，程序读入
    grammar = read_grammar()
    # 判断左递归，并返回结果
    judge_result(grammar)
    # 打印消除左递归后的结果
    print("\n消除左递归后的结果为：")
    for each in result_1:
        print(each)
    # 提取左因子
    get_left_factor(result_1)
    print("\n提取左因子后的结果为：")
    for each in result_2:
        print(each)
